package NowCoder.DynamicPlanning;

/**
 * JD1 年终奖
 * 简单  通过率：32.18%  时间限制：3秒  空间限制：32M
 * 知识点 动态规划
 * 描述
 * 小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，
 * 上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，
 * 到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
 *
 * 给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
 * https://www.nowcoder.com/practice/72a99e28381a407991f2c96d8cb238ab?tpId=134&tqId=33854&ru=/exam/oj
 */
public class 年终奖_JD1 {
    public int getMost(int[][] board) {
        // write code here
        if(board.length == 2 && board[0].length == 2){
            return board[1][0] > board[0][1] ? board[1][0] + board[1][1] + board[0][0] : board[0][1] + board[1][1] + board[0][0];
        }
        if(board.length == 2){//当行等于2，列不等于2的时候
            int sum = board[0][0];
            for(int i = 0;i < board[0].length;i++){
                sum += board[1][i];
            }

            int[][] board1 = clone(board,true);

            return Math.max(sum, getMost(board1) + board[0][0]);
        }
        if(board[0].length == 2){//当列等于2，行不等于2的时候
            int sum = board[0][0];
            for(int i = 0;i < board.length;i++){
                sum += board[i][1];
            }
            int[][] board1 = clone(board,false);
            return Math.max(sum, getMost(board1) + board[0][0]);
        }

        return getMost(clone(board,true)) > getMost(clone(board,false)) ? getMost(clone(board,true)) + board[0][0] : getMost(clone(board,false)) + board[0][0];
    }

    public static int[][] clone(int[][] board,boolean isRight){
        if(isRight){
            int line = board.length;
            int arrange = board[0].length;
            int[][] board1 = new int[line][arrange - 1];
            for(int i = 0;i < line;i++){
                for(int j = 1;j < arrange;j++){
                    board1[i][j - 1] = board[i][j];
                }
            }

            return board1;
        }else{
            int line = board.length;
            int arrange = board[0].length;
            int[][] board1 = new int[line - 1][arrange];
            for(int i = 1;i < line;i++){
                for(int j = 0;j < arrange;j++){
                    board1[i - 1][j] = board[i][j];
                }
            }
            return board1;
        }
    }
}
